Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Wir können langsam anfangen. Das Programm für diese Woche ist das CG-Verfahren und zwar werden

wir heute versuchen das CG-Verfahren zu verstehen, also das Verfahren der konjugierten Gradienten und

damit unser erstes sozusagen einigermaßen State-of-the-Art-Verfahren und dann, wenn wir

dann uns vermutlich dann nächstes Mal überlegt haben, wie man das mit Vorkonditionierung kombiniert,

dann haben wir schon wirklich ein Recht oder sehr gutes Verfahren, zumindest aus der Klasse

der Blackbox-Verfahren für große dünnbesetzte Gleichungssysteme. Ja, was wir jetzt noch

nachtragen müssen ist, was ist überhaupt eine sinnvolle Datenstruktur? Wir haben ja diese Hoffnung,

dass bei dünnbesetzten Matrizen die iterativen Verfahren, so wie wir sie jetzt haben, vielleicht

konkurrenzfähig oder vielleicht sogar langfristig überlegen sein können, weil sie eben nur Matrix

mal Vektor als Grundoperation brauchen. Das heißt also etwas, was man so gestalten kann,

dass man wirklich nur auf die nicht-Null-Elemente, das ist etwas, was ich demnächst immer nur noch

Einträge nennen werde, der Matrix zugreifen kann, aber dann braucht man natürlich auch eine

Datenstruktur, die das unterstützt. Denn um zu verhindern, dass zum einen, und das ist bei großen

Matrizen durchaus, von Bedeutung nicht unnütz Nullen abspeichert, also bei den ganz großen

Probleme wird man nicht in einer zweidimensionalen Feldstruktur überhaupt speichern können,

in einem üblichen Hauptspeicher und zum anderen natürlich nicht solche Nullmal-Operationen

unnötigerweise mitzuziehen. Wie kann so eine kompakte Datenstruktur aussehen? Da gibt es viele

Varianten, die letztlich alle auf das Gleiche hinauslaufen. Also sie haben ja schon sozusagen

implizit mit so etwas gearbeitet, indem diese Struktur SPARS, die Matlab zur Verfügung stellt,

benutzt worden ist. Das ist letztendlich, ohne dass der Benutzer das merkt, eine solche Struktur.

Ich bin mir jetzt nicht sicher, ob identisch mit der, die ich jetzt gleich ansprechen werde oder

eine minimale Modifikation davon. Aber wir hatten das ja schon mal ausführlich und prinzipiell

besprochen. Wir wollen jetzt natürlich nicht Matlab benutzen, weil wir eben ein Werkzeug brauchen,

was all diese Fähigkeiten hat. Gut, dann könnten wir nach Hause gehen, denn da müssen wir überhaupt

nichts über Verfahren wissen, denn Matlab stellt eh alles zur Verfügung. Vorausgesetzt natürlich,

man wendet es sinnvoll an und für nicht sinnvolle Anwendungen hatten wir ja auch schon Beispiele

gesehen. Aber uns geht es ja darum, so ein bisschen das Innenleben auch zu verstehen. Also wie kann man

eine dünn besetzte Matrix speichern? Das Ziel muss ja sein, wirklich nur die Einträge, die nicht

null Elemente zu speichern. Und zwar, man macht das in einem dimensionalen Feld. Also wir haben eine

Matrix A, sagen wir mal in der üblichen Notation A, I, J. Eine Matrix, ob das jetzt real oder komplex ist,

ist egal. Ich machs mal quadratisch, aber das muss auch nicht quadratisch sein. Das kann man auch auf

Rechtex-Matrizen erweitern, aber uns interessieren jetzt in dem Kontext ja sowieso erstmal nur

quadratische Matrizen. Und was man also macht, man macht eine Liste der Einträge. Was ist das?

Man braucht ein eindimensionales Feld. Das heißt, das nenne ich mal jetzt A-List. Das hat groß N

Positionen. Also ich lasse jetzt hier den Index von 1 laufen, weil wir ja Matlab machen und nicht C.

Es gibt das Ganze auch mit der Variante, wo die Indizes von 0 anfangen. Also ich hoffe, dass Sie

dann zwischen diesen beiden Varianten auch hin und her gehen können. Okay, was ist das groß N?

Das soll eben die Anzahl aller Einträge sein, aller von null verschiedenen Elemente, die ich zu

speichern habe. Und in dieser Liste speichere ich die nach irgendeinem Prinzip ab. Wenn man sich das

Leben schwer machen wollte, könnte man irgendeine Anordnung wählen, was typisch ist. Entweder man

macht es zeilenorientiert, so wie wir das jetzt hier machen wollen, oder macht es spaltenorientiert.

Das heißt also beim Zeilenorientierten geben wir einfach die erste Zeile von links nach rechts

durch. Schauen, wo die nicht null Einträge stehen, speichern die hier ab. Das heißt, der erste kommt

auf die Position 1, der zweite auf die Position 2 und so weiter. Dann kommt die nächste Zeile dran,

also erste Zeile von links nach rechts und so weiter, bis schließlich wir bei der enden Zeile sind

und die dann auch von links nach rechts. Wie gesagt, man könnte das genauso gut spaltenorientiert

machen. Jetzt für Matrix mal Vektor ist die zeilenorientierte Schreibweise, die Sichtweise,

die etwas angenehmere. So, jetzt haben wir sozusagen mit minimalem Aufwand die Elemente

gespeichert. Sind wir fertig, oder? Genau, jetzt müssen wir es auch wieder finden, denn das ist